package 算法.leetcode.offer;

import 算法.leetcode.offer.base.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author lchenglong
 * @date 2022/4/27
 */
public class Offer32_III {

    public static void main(String[] args) {
        Offer32_III instance = new Offer32_III();
        // [3,9,20,null,null,15,7]
        List<Integer> list = new ArrayList<Integer>();
        list.add(3);
        list.add(9);
        list.add(20);
        list.add(null);
        list.add(null);
        list.add(15);
        list.add(7);
        TreeNode root = TreeNode.init(list);
        List<List<Integer>> ans = instance.levelOrder(root);
        System.out.println(Arrays.toString(ans.toArray()));
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null)return new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int flag = 1;
        int size = queue.size();
        while (size>0){
            int[] list  = new int[size];
            for (int i=0;i<size;i++){
                TreeNode node = queue.poll();
                if (node!=null){
                    if (flag == -1) list[size-i-1] = node.val;
                    else list[i] = node.val;
                    if (node.left!=null)queue.add(node.left);
                    if (node.right!=null)queue.add(node.right);
                }
            }
           ans.add(Arrays.stream(list).boxed().collect(Collectors.toList()));
           flag*=-1;
           size = queue.size();
        }
        return ans;
    }
}
